package main

import (
	"fmt"
	. "local/algorithm/util"
	"strconv"
)

func str2tree(s string) *TreeNode {

	if 0 == len(s) {
		return nil
	}
	//初始化栈，其中存放的节点指针
	stack := []*TreeNode{}
	for i := 0; i < len(s); i++ {
		if s[i] == ')' {
			stack = stack[:len(stack)-1]
		} else if (s[i] >= '0' && s[i] <= '9') || s[i] == '-' { //当前位是0~9或-时，开启记录数字
			j := i
			for i+1 < len(s) && s[i+1] >= '0' && s[i+1] <= '9' { //数字后续由0~9组成时，继续扩展数字长度 且注意要先判断i+1<len(s)保证i有效
				i++
			}
			val, _ := strconv.Atoi(s[j : i+1])
			node := &TreeNode{Val: val}
			if len(stack) != 0 {
				parent := stack[len(stack)-1]
				if parent.Left == nil {
					parent.Left = node
				} else {
					parent.Right = node
				}
			}
			stack = append(stack, node)
		}
	}
	return stack[0]
}

func main() {
	fmt.Println(str2tree("4(2(3)(1))(6(5))"))
}
